package tree;

import java.util.Comparator;

/**
 * @author 陈艺博
 * @date 2021-02-28 14:51
 * @description 二叉搜索树
 **/
public class BinarySearchTree<E> extends BinaryTree {
    private Comparator<E> comparator;

    public BinarySearchTree() {
        this(null);
    }

    public BinarySearchTree(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    /**
     * 添加元素
     *
     * @param element 指定元素
     */
    public void add(E element) {
        elementNotNullCheck(element);

        //添加第一个节点
        if (root == null) {
            root = new Node<>(element, null);
            size++;
            return;
        }

        // 添加的不是第一个节点
        // 找到父节点
        Node<E> parent = root;
        Node<E> node = root;
        int cmp = 0;
        // 大小标识
        do {
            cmp = compare(element, node.element);
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {//相等
                node.element = element;
                return;
            }
        } while (node != null);

        // 插入父节点的对应位置
        Node<E> newNode = new Node<>(element, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;
    }

    /**
     * 删除元素
     *
     * @param element 指定元素
     */
    public void remove(E element) {
        remove(node(element));
    }

    /**
     * 通过Node删除元素
     */
    private void remove(Node<E> node) {
        if (node == null) {
            return;
        }
        size--;

        if (node.isTowChildren()) {//度为2的节点
            // 找到后继节点
            Node<E> successor = successor(node);
            // 使用后继节点的值，覆盖当前度为2节点的值
            node.element = successor.element;
            //删除后继节点
            node = successor;
        }

        //删除node节点（node的度必然是1后者0）
        Node<E> replacement = node.left != null ? node.left : node.right;

        if (replacement != null) {//node度为1
            //更改parent
            replacement.parent = node.parent;
            // 更改parent的left、right
            if (node.parent == null) {//node度为1并且是根节点
                root = replacement;
            } else if (node == node.parent.left) {
                node.parent.left = replacement;
            } else {
                node.parent.right = replacement;
            }
        } else if (node.parent == null) {//度为0，并且是根节点
            root = null;
        } else {//node是叶子节点，但是不是根节点
            if (node == node.parent.left) {
                node.parent.left = null;
            } else {
                node.parent.right = null;
            }
        }
    }

    /**
     * 通过值获取指定Node
     *
     * @param element Node.element
     * @return Node
     */
    private Node<E> node(E element) {
        Node<E> node = root;
        while (node != null) {
            // 0 相同 1 element大，
            int cmp = compare(element, node.element);
            if (cmp == 0) {
                return node;
            }
            if (cmp > 0) {
                node = node.right;
            } else {//cmp<0
                node = node.left;
            }
        }
        return null;
    }

    /**
     * 是否包含某个元素
     *
     * @param element 指定元素
     */
    public boolean contains(E element) {
        return node(element) != null;
    }

    /**
     * 比较e1和e2的值
     *
     * @param e1
     * @param e2
     * @return e1==e2 return 0; e1>e2 return >0; e1<e2 return <0
     */
    private int compare(E e1, E e2) {
        if (comparator != null) {
            // 使用自定义比较器
            return comparator.compare(e1, e2);
        }
        return ((Comparable<E>) e1).compareTo(e2);
    }
}
